// 20. 有效的括号
// https://leetcode.cn/problems/valid-parentheses/
// 简单,给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
// 示例 1：
// 输入：s = "()"
// 输出：true
// 示例 2：
// 输入：s = "()[]{}"
// 输出：true
// 示例 3：
// 输入：s = "(]"
// 输出：false

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> stkPa;
        map<char,char> mapPa;
        mapPa[')'] = '(';
        mapPa[']'] = '[';
        mapPa['}'] = '{';
        for(auto c : s) {
            if (c == '(' || c == '[' || c == '{') {
                stkPa.push(c);
            } else {
                if (stkPa.size() > 0 && mapPa[c] == stkPa.top()) {
                    stkPa.pop();
                } else {
                    return false;
                }
            }
        }
        return stkPa.size() == 0;
    }
};


int main(){
    Solution sol;
    sol.isValid("[");
    return 0;
}
